/***
7-9 列出所有祖先结点 (30 分)
对于给定的二叉树，本题要求你按从上到下顺序输出指定结点的所有祖先结点。

输入格式:
首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。

随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 "-"。编号间以 1 个空格分隔。

最后一行给出一个结点的编号i（0≤i≤N-1）。

输出格式:
在一行中按规定顺序输出i的所有祖先结点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例:
7
2 -
- 6
- -
0 5
- -
4 1
- -
4
结尾无空行
输出样例:
3 5
结尾无空行
***/
#include "stdio.h"
#include "stdlib.h"

int main(int argc, char const *argv[])
{
    int *p,*stack;
    int top;
    int i, N,target;
    char s[10];
    // freopen("d:\\a.txt","r",stdin);
    gets(s);
    N=atoi(s);
    p = (int *)malloc(sizeof(int) * N);
    stack = (int *)malloc(sizeof(int) * N);
    for (i = 0; i < N; i++)
        p[i] = i;
    for (i = 0; i < N; i++)
    {
        gets(s);
        if (s[0] != '-')
            p[s[0] - '0'] = i;
        if (s[2] != '-')
            p[s[2] - '0'] = i;
    }
    gets(s);
    target=s[0]-48;
    if(N==1)return 0;//仅有一个结点
    top=-1;
    i=target;
    while(p[i]!=i){
        top++;
        stack[top]=p[i];
        i=p[i];
    }
    while(top>=0){
        if(top>0)
            printf("%d ",stack[top]);
        else
            printf("%d\n", stack[top]);
        top--;
    }
    free(stack);
    free(p);
    return 0;
}
